package com.wxweven.algorithm.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wxweven
 */
public class LC39组合总和 {

    /*
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的数字可以无限制重复被选取。
     *
     * 说明：
     *
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。 
     * 示例 1：
     *
     * 输入：candidates = [2,3,6,7], target = 7,
     * 所求解集为：
     * [
     *   [7],
     *   [2,2,3]
     * ]
     * 示例 2：
     *
     * 输入：candidates = [2,3,5], target = 8,
     * 所求解集为：
     * [
     *   [2,2,2,2],
     *   [2,3,3],
     *   [3,5]
     * ]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/combination-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * 视频讲解：https://www.youtube.com/watch?v=aBL-aNWNmB4
     */

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curSeq = new ArrayList<>();

        if (candidates == null || candidates.length == 0) {
            return res;
        }

        helper(candidates, target, 0, res, curSeq);

        return res;
    }

    public void helper(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> curSeq) {
        if (target == 0) {
            // 当前元素并不在curSeq中
            res.add(new ArrayList<>(curSeq));
        } else if (target > 0) {
            // 因为当前元素并不在curSeq中，所以这里的条件是 target > 0

            for (int i = index; i < candidates.length; i++) {
                curSeq.add(candidates[i]);

                // 注意，题目中说数组中的同一个元素可以重复用，所以递归算法里，index 还是 i
                // 如果不能重复用，那这里的index就是 i + 1
                helper(candidates, target - candidates[i], i, res, curSeq);

                // 回溯算法，删除最后一个元素，回到上层
                curSeq.remove(curSeq.size() - 1);
            }
        }
    }
}